package com.剑指offer一;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 剑指 Offer 06. 从尾到头打印链表
 * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）
 * @author leon
 * @date 2021年12月15日 18:33
 */
public class ReversePrint {
    /**
     * 头插法
     * @param head
     * @return
     */
    public int[] reversePrint(ListNode head) {
        // 哑结点
        ListNode dummy = new ListNode(0);
        // 当前结点赋值给移动结点，不改变头结点的指向
        // 错误:地址赋值还是同一个对象，也不能改变头结点移动的事实
        ListNode moveNode = head;
        int n = 0;
        while (moveNode!=null){
            n++;
            ListNode node = moveNode;
            moveNode = moveNode.next;
            node.next = dummy.next;
            dummy.next = node;
        }
        moveNode = dummy.next;
        int[] ans= new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = moveNode.value;
            moveNode = moveNode.next;
        }
        return ans;

    }


    /**
     * 栈
     * @param head
     * @return
     */
    public int[] reversePrint1(ListNode head){
        Stack<Integer> stack =new Stack<>();

        while (head!=null){
            stack.push(head.value);
            head = head.next;
        }

        int[] ans= new int[stack.size()];
        for (int i = 0; i < stack.size(); i++) {
            ans[i] = stack.pop();
        }
        return ans;

    }

    /**
     * 递归
     * @return
     */
    private List<Integer> list = new ArrayList<>();;
    public int[] reversePrint2(ListNode head){
        recur(head);
        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;

    }
    private void recur(ListNode node){
        if(node == null){
            return;
        }
        recur(node.next);
        list.add(node.value);
    }

    class ListNode{
        int value;
        ListNode next;
        ListNode(int x){
            value = x;
        }
    }
}
